package org.example.Soution003;


import java.util.*;

public class DynamicProgrammingDict {
    public static void main(String[] args) {
        DynamicProgrammingDict d = new DynamicProgrammingDict();
        String s="catsandog";
        List<String> wordDict = new ArrayList<String>();
        wordDict.add("cats");
        wordDict.add("cat");
        wordDict.add("dog");wordDict.add("sand");wordDict.add("and");
        System.out.println(d.wordBreak(s, wordDict));
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        char[] chars = s.toCharArray();
        boolean[] res=new boolean[s.length()+1];
        res[0]=true;
        Set<String> wordSet=new HashSet<String>();
        Set<Integer> lenSet=new HashSet<Integer>();
        for(String word:wordDict){
            wordSet.add(word);
            lenSet.add(word.length());
        }
        int flag=0;
        while(flag<s.length()){
            if(res[flag]){
                for(int len:lenSet){
                    if(flag+len>s.length()) continue;
                    String word=s.substring(flag,flag+len);
                    if(wordSet.contains(word)){
                        res[flag+len]=true;
                    }
                }
            }
            flag++;
        }
        return res[s.length()];
    }
}
